package api_day04;
/*
    数据结构之链表结构实现集合功能
    @author Dalwin
    @date 2022.7.27
 */
public class MyLinkedList {
    //头节点
    Node head;
    //集合元素个数
    private int size;
    //无参构造方法
    public MyLinkedList() {
        head = new Node();
        size = 0;
    }
    //向集合中末尾添加元素
    public void add(Object object){
        Node current = head;
        while (current.next != null){
            current = current.next;
        }
        current.next = new Node(object);
        size++;
    }
    //向集合index的位置中插入obj元素
    public void insert(int index,Object object){
        if (outOfBound(index)) return;
        Node indexNode = find(index-1);
        Node newNode = new Node(object);
        newNode.next = indexNode.next;
        indexNode.next = newNode;
        size++;
    }
    //从集合中获得指定index位置的元素
    public Object get(int index){
        if (outOfBound(index)) return null;
        Node indexNode = find(index);
        return indexNode.data;
    }
    //替换指定index位置上的元素为obj，并且返回被替换的元素
    public Object replace(int index,Object object){
        if (outOfBound(index)) return null;
        Node indexNode = find(index-1);
        Object o = indexNode.next.data;
        indexNode.next.data = object;
        return o;
    }
    //删除指定位置index上的元素，并且返回删除元素
    public Object remove(int index){
        if (outOfBound(index)) return null;
        Node current = find(index-1);
        Node returnNode = current.next;
        current.next = current.next.next;
        size--;
        return returnNode.data;
    }
    //删除第一个指定元素
    public boolean remove(Object object){
        if (contain(object)){
            Node current = head;
            while (! current.next.data.equals(object)){
                current = current.next;
            }
            current.next = current.next.next;
            size--;
            return true;
        }
        return false;
    }
    //获得集合中的元素个数
    public int size(){
        return size;
    }
    //判断集合中是否存在指定元素
    public boolean contain(Object object){
        Node current = head;
        //这一部分也可以用for循环完成for(Node current = head;current.next != null;current = current.next)
        while (current.next != null){
            current = current.next;
            if (current.data == object) return true;
        }
        return false;
    }
    //判断集合是否为空
    public boolean isEmpty(){return size == 0;}
    //下标越界判断
    public boolean outOfBound(int index){
        return index < 0 || index >= size;
    }
    //定位到指定位置
    private Node find(int index){
        Node current = head.next;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current;
    }
    //打印出在集合中的有效元素
    @Override
    public String toString() {
        StringBuilder out = new StringBuilder("[");
        Node current = head;
        while (current.next != null){
            current = current.next;
            out.append(current.data + ",");
        }
        out.deleteCharAt(out.length()-1);
        out.append("]");
        return out.toString();
    }

    //节点内部类
    private class Node{
        Object data;
        Node next;
        public Node() {
        }
        public Node(Object data) {
            this.data = data;
        }
    }
}